package leetcode100;

import lanqiao.C;

import java.util.LinkedList;

public class lc046 {


    private final int[][] offsets = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public static void main(String[] args) {
        char[][] board = {{'A', 'B', 'C', 'E'}
                        , {'S', 'F', 'C', 'S'}
                        , {'A', 'D', 'E', 'E'}};
        String word = "ABCCDE";
        boolean res = new lc046().exist(board, word);
        System.out.println("res = " + res);
    }

    public boolean exist(char[][] board, String word) {
        int row = board.length;
        int col = board[0].length;
        int[][] visited = new int[row][col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                boolean res = dfs(i, j, 0, word, visited, board);
                if (res) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(int i, int j, int index, String word, int[][] visited, char[][] board) {
//        System.out.print("index: "+index+"  ");
//        System.out.print("i = " + i);
//        System.out.println(" j = " + j);
        if (word.length() == index) {
            return true;
        }
        if (board[i][j] == word.charAt(index)) {
            visited[i][j] = 1;
            if (word.length() == index+1) {
                return true;
            }
            for (int[] offset : offsets) {
                if ((i + offset[0] >= 0) && (i + offset[0] < board.length)
                        && (j + offset[1] >= 0) && (j + offset[1] < board[0].length)
                        && (visited[i+offset[0]][j+offset[1]] == 0)) {

                    boolean res = dfs(i + offset[0], j + offset[1], index + 1, word, visited, board);
                    if (res) {
                        return true;
                    }
                }
            }
            visited[i][j] = 0;
        }
        return false;
    }
}
